import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

import org.junit.Test;

public class MyTest { 
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        ArrayList<int[]> arrayList=new ArrayList<int[]>();
        DFS(root, arrayList, 0, 0);
        arrayList.sort(
            (first,second)->{
                if(first[1]-second[1]==0){
                    if(first[0]-second[0]==0){
                        return first[2]-second[2];
                    }else{
                        return first[0]-second[0];
                    }
                }else{
                    return first[1]-second[1];
                }
            }
        );
        ans.add(new ArrayList<Integer>());
        ans.get(0).add(arrayList.get(0)[2]);
        for(int i=1;i<arrayList.size();i++){
            if(arrayList.get(i)[1]==arrayList.get(i-1)[1]){
                ans.get(ans.size()-1).add(arrayList.get(i)[2]);
            }else{
                ans.add(new ArrayList<Integer>());
                ans.get(ans.size()-1).add(arrayList.get(i)[2]);
            }
        }
        return ans;
    }
    
    private void DFS(TreeNode root,ArrayList<int[]> arrayList,int row,int col){
        if(root==null){
            return;
        }
        arrayList.add(new int[]{row,col,root.val});
        DFS(root.left, arrayList, row+1, col-1);
        DFS(root.right, arrayList, row+1, col+1);
    }

    public int[] sortedSquares(int[] nums) {
        int[] ans=new int[nums.length];
        int k=0;
        while(nums[k++]<0);
        int p=k-1;
        int i=0;
        while(p>=0&&k<nums.length){
            if(nums[p]<nums[k]){
                ans[i++]=nums[p--];
            }else{
                ans[i++]=nums[k++];
            }
        }
        if(p<0){
            while(i<nums.length){
                nums[i++]=nums[k++];
            }
        }else{
            while(i<nums.length){
                nums[i++]=nums[p--];
            }
        }
        return ans;
    }

    public void rotate(int[] nums, int k) {
        int left=0,right=nums.length-1,temp;
        while(left<right){
            temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right--;
        }
        right=k-1;
        while(left<right){
            temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right--;
        }
        left=k;
        right=nums.length-1;
        while(left<right){
            temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right--;
        }
    }


    @Test
    public void test(){

    }
}
